package thirteenth_day;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
 */
public class ReverseOnlyLetters {
    public static String reverseOnlyLetters(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        // 双指针
//        int left = 0;
//        int len = s.length();
//        int right = len - 1;
//        StringBuilder str = new StringBuilder(s);
//        while (left < right) {
//            // 寻找字母
//            while (left < right && !Character.isLetter(s.charAt(left))) {
//                left ++;
//            }
//            while (right > left && !Character.isLetter(s.charAt(right))) {
//                right --;
//            }
//            // 更换位置
//            char l = s.charAt(left);
//            char r = s.charAt(right);
//            str.insert(right, l);
//            str.deleteCharAt(right + 1);
//            right --;
//            str.insert(left, r);
//            str.deleteCharAt(left + 1);
//            left ++;
//        }
//        return str.toString();

        // 使用栈存储字母
//        Deque<Character> deque = new ArrayDeque<>(); // 字母栈
//        char[] arr = s.toCharArray();
//        for (char c : arr) {
//            if (Character.isLetter(c)) {
//                deque.push(c);
//            }
//        }
//        StringBuilder str = new StringBuilder();
//        // 存完之后刚好出栈是倒叙的
//        for (char c : arr) {
//            if (!Character.isLetter(c)) {
//                str.append(c);
//            } else {
//                str.append(deque.pop());
//            }
//        }
//        return str.toString();

        // 反转指针
        int right = s.length() - 1; // 从后遍历字符串
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!Character.isLetter(c)) {
                str.append(c);
            } else {
                // 如果是字母则从后面找一个字母代替现在的位置
                while (right >= 0 && !Character.isLetter(s.charAt(right))) {
                    right --;
                }
                // 找到后面的字母
                str.append(s.charAt(right));
                right --;
            }
        }
        return str.toString();
    }

    public static void main(String[] args) {
//        String s = "a-bC-dEf-ghIj"; // "j-Ih-gfE-dCba"
        String s = "Test1ng-Leet=code-Q!"; // "Qedo1ct-eeLg=ntse-T!"
//        String s = "--+";
        System.out.println(reverseOnlyLetters(s));
    }
}
